1. Field of the Invention
The present invention relates to a path compression system for compressing paths in graph information and a path compression method thereof and more particularly to a path compression system for compressing paths included in data (called graph information, hereinafter) having such a graphic structure as a logic circuit and a path compression method thereof.
2. Description of the Prior Art
According to conventional path compression systems, it has been necessary to hold the halfway result of a search on the way of a path upon search of the path. In case the halfway result is obtained by a computer, the large capacity of a memory has been needed. In prior art documents of the above-described types of compression systems is included "Method for Increasing Speed of Timing Analysis System HEART (1) to Large Scale Circuit" (a Fifth National Conference of Information Processing Society of Japan 7F-6) (referred to as a prior art document 1, hereinafter).
Further, a path compression system has been known in which the halfway result of a search is not held during the search of the path. In this case, however, much processing time has been required. As prior art documents of this kind of compression system is included "Delay Time Analysis System-NELTAS 2-" (Information Processing Society of Japan, Design Automation Seminar Document, Design Automation 14-3, 1982) (referred to as a prior art document 2, hereinafter).
Furthermore, in attempting to reduce the capacity of a memory, a path compression system for compressing data has been known, however, the 1 conventional compression system of this kind has not performed a sufficient compression ratio. As prior arts of this kind of compression system is incorporated Japanese Unexamined Patent Publication No. Shouwa 62-202268 (referred to as a prior art document 3, hereinafter).
As described above, in the case of a technique disclosed in the prior art document 1 in the conventional path compression systems mentioned above, the halfway result of a search must be held during the search of the path. Therefore, if the halfway result is obtained on a computer, a large capacity of a memory will be undesirably needed.
Further, in the case of a technique disclosed in the prior art document 2, there has been disadvantageously a problem that much processing time is taken.
Furthermore, in the case of a technique disclosed in the prior art document 3, there has arisen an inconvenience that a compression cannot be completed even when data is compressed in order to reduce the capacity of a memory.